package offer;
//复杂链表的复制
public class T26 {

public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}


        public RandomListNode Clone1(RandomListNode pHead)
        {
             RandomListNode randomListNode[] = new RandomListNode[1000];
             RandomListNode  node[] = new RandomListNode[1000];
             randomListNode[0] = new RandomListNode(1);
             int cnt = 1;
             while (pHead!=null) {
                 randomListNode[cnt] = new RandomListNode(pHead.label);
                 randomListNode[cnt-1].next = randomListNode[cnt];
                 node[cnt] = pHead;
                 cnt++;
                 pHead = pHead.next;
             }

            for (int j = 1; j < cnt; j++) {
                for (int i=1;i<cnt;i++) {
                    if (node[j].equals(node[i].random)) {
                        randomListNode[i].random = randomListNode[j];
                    }
                }
            }
             return randomListNode[1];
        }


   public RandomListNode Clone(RandomListNode pHead) {
       if (pHead==null) return null;
        RandomListNode root = pHead;
        while (pHead!=null) {
            RandomListNode temp = new RandomListNode(pHead.label);
            temp.next = pHead.next;
            pHead.next = temp;
            pHead = temp.next;
        }
        pHead = root;
       while (pHead!=null) {
           if (pHead.random!=null)
           pHead.next.random = pHead.random.next;
           pHead = pHead.next.next;
       }
       pHead = root;
       RandomListNode node = root.next;
       while (pHead!=null) {
           RandomListNode t = pHead.next;
           RandomListNode head = t.next;
           if (head!=null)
           t.next = head.next;
           pHead.next = head;
           pHead = head;

       }
       return node;
   }

}
